package Data_Structure.Sort;

import java.util.Arrays;

/**
 * @className: ShellSort
 * @author: 芃
 * @description: 希尔排序实现
 * @date: 2023/8/20 17:18
 */
//主要思想：
//假设有N个数据，我们了解到对于直接插入排序来说，数据越有序越快
//因此，我们对这N个数据进行分组排序，即在组内进行排序，排序完成后再减少组数
//假设组数为gap，随着gap的递减，数据逐渐趋于有序，当gap为1时，对全组数据再进行直接插入排序
//每次分组后进行排序时，依然采用直接插入排序的方式
//综上所述，希尔排序就是对直接插入排序的一种优化排序，其本质依然是直接插入排序
//
//空间复杂度: O(1) 未开辟额外空间
//时间复杂度: O(n^1.3 ~ n^1.5)
//稳定性:不稳定的
//看一个算法是否稳定，看在比较的过程当中，是否发生了跳跃式的交换，如果发生了跳跃式的交换，那么就是不稳定的排序
public class ShellSort {
    public static void shellSort(int[] arr){
        int gap = arr.length;
        while (gap > 1){
            shell(arr,gap);
            gap /= 2;
            System.out.println(Arrays.toString(arr));
        }
        shell(arr,1);//保证最后是一组
    }
    /**
     * @param array: 待排序序列
     * @param gap: 组数
     * @author: zyp19
     * @description:
     * @date: 2023/8/27 9:56
     */
    public static void shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (tmp < array[j]){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }
}
